/*
https://leetcode.cn/problems/burst-balloons/description/
312. 戳气球
方钊堉 2024.10.19
区间dp
*/
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        
        // 在原数组两端各添加一个虚拟气球，值为1
        vector<int> extendedNums(n + 2);
        for (int i = 0; i < n; i++) {
            extendedNums[i + 1] = nums[i];
        }
        extendedNums[0] = 1;
        extendedNums[n + 1] = 1;

        // dp[i][j] 表示开区间 (i, j) 中戳破气球可以获得的最大硬币数量
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        // 第一层循环控制区间长度
        for (int length = 3; length <= n + 2; length++) {
            // 第二层循环控制开区间的起始位置
            for (int start = 0; start <= n + 2 - length; start++) {
                int end = start + length - 1; // 计算区间的结束位置
                // 第三层循环枚举区间内的最后一个被戳破的气球
                for (int lastBalloon = start + 1; lastBalloon <= end - 1; lastBalloon++) {
                    // 更新 dp[start][end] 的值
                    dp[start][end] = max(dp[start][end], 
                                         dp[start][lastBalloon] + 
                                         extendedNums[start] * extendedNums[lastBalloon] * extendedNums[end] + 
                                         dp[lastBalloon][end]);
                }
            }
        }

        // 返回整个区间 [0, n + 1] 中的最大硬币数量
        return dp[0][n + 1];
    }
};